//此算法是时间复杂度为n^2，一般适合稠密图，但是只能在全正权边上进行操作
//此算法确定某一路径为最短路的原理是，在图中全部为最短路的前提下，我作为现存未确定的最短路，其他的点不论怎么优化我，也不可能比我现在更短
#include <iostream>
#include <cstring>
using namespace std;

const int N = 510;
const int INF = 0x3f3f3f3f;
int g[N][N]; //稠密图用邻接举证进行存储
int dist[N]; //存储每个点现阶段的最短路径
bool st[N];  //记录已经确定了是完美最短的点
int n, m;    //获取点数目和边数目
int x, y, z; //获取一条边的信息，包括起始点，终止点，以及权值

int dijkstra(int Begin = 1, int End = n)
{
    dist[Begin] = 0;                //到自己的距离为0
    for (int i = 0; i < n - 1; ++i) //循环n-1次，每次确定到一个点的最短路径，减去的那一次是Begin自己
    {
        int t = -1;                  //选择这次被确定的点
        for (int j = 1; j <= n; ++j) //遍历所有点
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        st[t] = true; //选定的这个为已确定最短路
        if (t == End)
            return dist[End]; //一个小优化，因为只要确定了n的最短路这题就可以写出来了，理论上这题可以确定到任意位置的最短路径
        for (int j = 1; j <= n; ++j)
            dist[j] = min(dist[j], dist[t] + g[t][j]); //使用新确认的点来优化其他点
    }
    return dist[End];
}

int main()
{
    memset(g, 0x3f, sizeof g);       //在输入边之前每个点相互独立
    memset(dist, 0x3f, sizeof dist); //现阶段每个点到1的最短路径都假设为INF
    memset(st, false, sizeof st);    //现阶段所有点都是还没有确定最短路径
    cin >> n >> m;
    while (m--)
    {
        cin >> x >> y >> z;
        g[x][y] = min(g[x][y], z); //重边只选最短边
    }
    int t = dijkstra();
    if (t == INF)
        cout << -1;
    else
        cout << t;
    return 0;
}
